package puzzle.projecteuler.p200;


public class Problem149B {
	
	/**
	 * answer	: 
	 * time cost:  ms
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
//		System.out.println(dmax(new long[] {-2,5,3,2,9,-6,5,1,3,2,7,3,-1,8,-4,8}, 4));
		System.out.println(dmax(loadData(), 2000));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	private static long[] loadData() {
		long[] a = new long[4000000];
		for (int k = 0; k < 55; k ++) {
			long x = (200003*(k+1))%1000000;
			long y = ((((300007*(k+1))%1000000)*(k+1))%1000000)*(k+1);
			a[k] = (100003 - x + y%1000000)%1000000 - 500000;
		}
		for (int k = 55; k < a.length; k ++) {
			a[k] = (a[k-24] + a[k-55]  + 1000000)%1000000 - 500000;
		}
		return a;
	}
	/**
	 * 计算数组a中，连续和的最大值
	 * @param a
	 * @return
	 */
	private static long dmax(long[] a) {
		int[] s = new int[a.length];
		for (int i = 0; i < s.length; i ++) s[i] = i;
		return dmax(a, s, 0, s.length-1);
	}

	private static long dmax(long[] a, int[] s) {
//		for (int i = 0; i < s.length; i ++) {
//			System.out.print(String.format("a[%2d]=%3d\t", s[i], a[s[i]]));
//		}
		long r = dmax(a, s, 0, s.length-1);
//		System.out.println("=" + r);
		return r;
	}
	/**
	 * 计算矩阵数组T中，连续和的最大值。
	 * @param a
	 * @param size
	 * @return
	 */
	private static long dmax(long[] m, int size) {
		long max = m[0]; 
		//horizontal
		for (int i = 0; i < size; i ++) {
			int[] s = new int[size];
			for (int j = 0; j < size; j ++) {
				s[j] = i*size + j;
			}
			long x = dmax(m, s);
			if (max < x) max = x;
		}
		//vertical
		for (int i = 0; i < size; i ++) {
			int[] s = new int[size];
			for (int j = 0; j < size; j ++) {
				s[j] = i + j*size;
			}
			long x = dmax(m, s);
			if (max < x) max = x;
		}
		//diagonal
		for (int i = 1; i <= size; i ++) {
			int[] s = new int[i];
			int index = (i-1)*size;
			for (int j = 0; j < s.length; j ++) {
				s[j] = index-(size-1)*j;
			}
			long x = dmax(m, s);
			if (max < x) max = x;
		}
		for (int i = 1; i <= size-1; i ++) {
			int[] s = new int[size-i];
			int index = (size-1)*size+i;
			for (int j = 0; j < s.length; j ++) {
				s[j] = index-(size-1)*j;
			}
			long x = dmax(m, s);
			if (max < x) max = x;
		}
		//anti-diagonal
		for (int i = 0; i < size; i ++) {
			int[] s = new int[size-i];
			for (int j = 0; j < s.length; j ++) {
				s[j] = i+(size+1)*j;
			}
			long x = dmax(m, s);
			if (max < x) max = x;
		}
		for (int i = 0; i < size-1; i ++) {
			int[] s = new int[i+1];
			int index = size*(size-i-1);
			for (int j = 0; j < s.length; j ++) {
				s[j] = index+(size+1)*j;
			}
			long x = dmax(m, s);
			if (max < x) max = x;
		}
		return max;
	}

	/**
	 * 数组a中，下标是s[x]~s[y]的数构成一个新数组T，该函数计算数组T中，连续和的最大值
	 * 分治
	 * @param a
	 * @param s
	 * @return
	 */
	private static long dmax(long[] a, int[] s, int x, int y) {
		
		if (x == y) {
			return a[s[x]];
		} else if (x == y-1) {
			long t = Math.max(a[s[x]], a[s[y]]);
			return Math.max(t, a[s[x]]+a[s[y]]);
		} else {
			int mid = (x+y)/2;
			long left = dmax(a, s, x, mid);
			long right = dmax(a, s, mid+1, y);
			long t = Math.max(left, right);
			//right max - left min
			long sum = 0;
			long lmin = sum;
			for (int i = x; i <= mid; i ++) {
				sum += a[s[i]];
				if (lmin > sum) lmin = sum;
			}
			
			sum += a[s[mid+1]];
			long rmax = sum;
			for (int i = mid+2; i <= y; i ++) {
				sum += a[s[i]];
				if (rmax < sum) rmax = sum;
			}
			
			return Math.max(t, rmax-lmin);
		}
	}
}
